package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author haomin
 * @date 2022/10/22 17:31
 **/
public class Day50_1_Num1235_JobScheduling {
    class Solution {
        public int jobScheduling(int[] st, int[] et, int[] pf) {
            int n = st.length;
            List<int[]> list = new ArrayList<>();
            for(int i = 0; i < n; ++i) list.add(new int[]{st[i], et[i], pf[i]});
            Collections.sort(list, (a, b) -> (a[1]-b[1]));
            int[] dp = new int[n+10];
            for(int i = 1; i <= n; ++i){
                int[] pre = list.get(i-1);
                int a = pre[0], b = pre[1], c = pre[2];
                dp[i] = Math.max(dp[i-1], c);
                int l = 0, r = i-1, mid;
                while(l < r){
                    mid = l + r + 1 >> 1;
                    if(list.get(mid)[1] <= a) l = mid;
                    else r = mid -1;
                }
                if(list.get(r)[1] <= a) dp[i] = Math.max(dp[i], dp[r+1] + c);
            }
            return dp[n];
        }
    }

    public static void main(String[] args) {
        int l = 0, r = 10;
        System.out.println(l + r + 1 >> 1);
        System.out.println(l + ((r-l)>>1));
    }
}